#include <iostream>
#include "linearList.h"
using namespace std;

// 顺序表
//  初始化顺序表
sequenceList::sequenceList(const int &capacity, const int &length, float arr[])
{
    maxCapcity = capacity;
    curNumberOfItem = length;
    myList = new float[maxCapcity]; // myList这个指针当做动态分配的链表

    for (int i = 0; i < curNumberOfItem && i < maxCapcity; ++i)
    {
        myList[i] = arr[i];
    }
}

// 销毁顺序表
sequenceList::~sequenceList()
{
    delete[] myList; // 把所有new出来的delete即可
}

// 添加元素到顺序表的尾部
bool sequenceList::addItem(const float &value)
{
    if (curNumberOfItem >= maxCapcity) // 元素的个数大于等于最大容量,就无法添加元素了
    {
        return false;
    }
    myList[curNumberOfItem++] = value;
    return true;
}

// 插入元素到index位置
bool sequenceList::insertItem(const int &index, const float &value)
{
    if (index < 0 || index > curNumberOfItem || curNumberOfItem >= maxCapcity)
    {
        return false;
    }

    for (int i = curNumberOfItem; i > index; --i)
    {
        myList[i] = myList[i - 1];
    }
    myList[index] = value;
    curNumberOfItem++;
    return true;
}

// 删除元素,返回删除位置，找不到返回-1
int sequenceList::deleteItem(const float &value)
{
    for (int i = 0; i < curNumberOfItem; ++i)
    {
        if (myList[i] == value) // 找到删除位置了
        {
            for (int j = i; j < curNumberOfItem - 1; ++j) // 后面的元素全部前移一位
            {
                myList[j] = myList[j + 1];
            }
            curNumberOfItem--;
            return i;
        }
    }
    return -1;
}

// 查找元素（按序号找）,成功返回true，值放在val中，失败返回false
bool sequenceList::locate(const int &index, float &val)
{
    if (index < 0 || index >= curNumberOfItem)
    {
        return false;
    }
    val = myList[index];
    return true;
}

// 查找元素（按值找）,返回找到位置，找不到返回-1
int sequenceList::locate(const float &value)
{
    for (int i = 0; i < curNumberOfItem; ++i)
    {
        if (myList[i] == value)
        {
            return i;
        }
    }
    return -1;
}

// 倒序排列元素（使用原空间）
void sequenceList::reverse()
{
    for (int i = 0; i < curNumberOfItem / 2; ++i)
    {
        swap(myList[i], myList[curNumberOfItem - 1 - i]);
    }
}

// 顺序表打印
void sequenceList::print()
{
    cout << curNumberOfItem << ":";

    for (int i = 0; i < curNumberOfItem - 1; i++)
    {
        cout << myList[i] << ",";
    }

    cout << myList[curNumberOfItem - 1] << endl;
}

// 链表

// 先实现节点的函数

listNode::listNode(float nodeData, listNode *succ) // 注意这里不能写成succ=NULL
{
    data = nodeData;
    next = succ;
}

listNode::~listNode() // 目前来看不需要操作
{
}

// 再实现链表的函数
linkList::linkList() // 初始化链表
{
    firstNode = new listNode(); // 这句话的意思是,创建一个节点(实际上这里就是头结点), 并让firstNode指向头结点,即firstNode就是头指针
    curNode = firstNode;
    lastNode = firstNode; // 当前指针和尾结点，现在都只能指向头节点
    listSize = 0;         // 所含的元素为0(头指针不是元素)
}

linkList::linkList(const int &size, float arr[]) // 带参数的初始化链表
{
    firstNode = new listNode(); // 创建头节点
    curNode = firstNode;        // 当前节点指向头节点
    lastNode = firstNode;       // 尾节点指向头节点
    listSize = 0;               // 初始化链表大小为0

    for (int i = 0; i < size; ++i)
    {
        tailInsertItem(arr[i]); // 通过尾插法将数组元素插入链表
    }
}

linkList::~linkList() // 销毁链表
{
    listNode *current = firstNode; // 定义一个指向链表头结点的指针
    while (current != NULL)
    {
        listNode *nextNode = current->next;
        delete current;     // 删除当前的节点
        current = nextNode; // 当前节点后移
    }
    firstNode = NULL; // 考虑一下这一步有无必要
    lastNode = NULL;
}

bool linkList::headInsertItem(const float &val) // 插入元素(头插法)
{
    listNode *newNode = new listNode(val, firstNode->next); // 这里实际上是两个语句.先创建了一个节点,这个节点的数据是val,这个节点的指针域(即这一个节点的下一个节点)是头结点的下一个节点(即首元节点),并让newNode指向这个被新创造出来的节点,这样这个新节点就成了首元节点,而原来的首元节点变成了第二个节点
    //注意,上面的代码不能改为下面的两行代码,否则会发生bug,这是因为直接定义的节点是在栈中的,函数运行完成之后会释放,那么newNode就成了悬空指针
    /*listNode a(val, firstNode->next);
    listNode* newNode=&a;*/
    if (newNode == NULL)
    {
        return false; // 给这个指针分配内存失败,返回false
    }
    firstNode->next = newNode; // 头节点指向新节点
    if (listSize == 0)
    {
        lastNode = newNode; // 如果链表为空,说明原来的尾结点是指向头节点的,那么现在链表不为空了,将尾节点指向新节点
    }
    listSize++;
    return true;
}

bool linkList::tailInsertItem(const float &val) // 插入元素(尾插法)
{
    listNode *newNode = new listNode(val, NULL); // 这里创建了一个节点,这个节点的指针域指向空
    if (newNode == NULL)
    {
        return false;
    }
    //这里的原因已经明白了,因为->本质上是(*firstNode).next,当listSize==0时,firstNode和lastNode都指向头结点,lastNode->next = newNode已经更改了头结点的指针域,注意,指针本身是没有指针域的,我们只是在通过指针间接操作节点,只要节点更改了,所有指向该节点的指针同步也会更改
    if (listSize == 0) // 如果原本的链表是空的,还需要更新下头节点的指向(令人奇怪的是,删掉这个语句也不影响正确性,暂时没搞懂是什么原因)
    {
        firstNode->next = newNode;
    }
    lastNode->next = newNode; // 让原来的尾结点的后继指针指向这个新节点
    lastNode = newNode;       // 让尾节点指向这个新节点
    listSize++;
    return true;
}

//
int linkList::insertItem(const int &index, const float &val) // 插入元素到index位置，成功返回插入位置，错误返回-1
{
    if (index < 0 || index > listSize)
    {
        return -1;
    }
    curNode = firstNode;
    for (int i = 0; i < index; i++)
    {
        curNode = curNode->next;
    }
    listNode *newNode = new listNode(val, curNode->next);
    if (newNode == NULL)
    {
        return -1; // 分配内存失败(即创建节点失败)
    }
    curNode->next = newNode;
    //原因如上
    if (index == 0) // 插入的位置是开头,这样就相当于头插了,我们还需要更改firstNode的指向(令人奇怪的是,这里没有这个条件也不会出错,暂时还未发现是什么原因)
    {
        firstNode->next = newNode;
    }
    if (index == listSize) // 插入的位置是末尾,这样就相当于尾插了,我们还需要更改lastNode
    {
        lastNode = newNode;
    }
    listSize++;
    return index;
}

int linkList::deleteItem(const float &val) // 删除元素,返回删除位置，找不到返回-1
{
    curNode = firstNode;
    int position = 0;
    while (curNode->next != NULL)
    {
        if (curNode->next->data == val) // 找到要删除的节点
        {
            listNode *tempNode = curNode->next; // 定义一个临时的指针,指向要被删除的节点
            curNode->next = tempNode->next;     // 跳过要删除的节点
            if (tempNode == lastNode)
            {
                lastNode = curNode;
            }
            delete tempNode;
            listSize--;
            return position;
        }
        // 如果没有找到要删除的节点,接着循环
        curNode = curNode->next;
        position++;
    }
    return -1; // 如果没有这个元素,那么就无法删除,返回-1
}

//
bool linkList::locate(const int &index, float &val) // 查找元素（按序号找）,成功返回true，值放在val中，失败返回false
{
    if (index < 0 || index >= listSize) // 超出索引范围
    {
        return false;
    }
    curNode = firstNode->next; // curNode指向第一个有效节点(即首元结点)
    for (int i = 0; i < index; i++)
    {
        curNode = curNode->next;
    }
    val = curNode->data;
    return true;
}

//
int linkList::locate(const float &val) // 查找元素（按值找）,返回找到位置，找不到返回-1
{
    curNode = firstNode->next; // curNode指向第一个有效节点(即首元结点)
    int position = 0;          // val这个元素所在的位置
    while (curNode != NULL)
    {
        if (curNode->data == val)
        {
            return position;
        }
        curNode = curNode->next;
        position++;
    }
    return -1;
}

void linkList::ascendingOrder() // 递增排序(这里用了简单的冒泡排序的思想)
{
    if (listSize <= 1) // 如果链表为空或只有一个节点，直接返回
    {
        return;
    }
    for (int i = 0; i < listSize - 1; i++)
    {
        listNode *current = firstNode->next; // 首元结点
        listNode *nextNode = current->next;  // 首元结点的下一个节点
        for (int j = 0; j < listSize - i - 1; j++)
        {
            if (current->data > nextNode->data)
            {
                swap(current->data, nextNode->data);
            }
            current = nextNode;
            nextNode = nextNode->next;
        }
    }
}

void linkList::reverse() // 反转链表
{
    if (firstNode->next == NULL)
        return; // 空链表，直接返回

    listNode *prev = NULL;
    listNode *current = firstNode->next;
    listNode *nextNode;

    lastNode = current; // 将最后一个节点更新为当前节点
    while (current != NULL)
    {
        nextNode = current->next; // 保存下一个节点
        current->next = prev;     // 反转当前节点的指针方向
        prev = current;           // 将prev移到当前节点
        current = nextNode;       // 将current移到下一个节点
    }
    firstNode->next = prev; // 更新链表的头指针
}

// 链表打印
void linkList::print()
{
    curNode = firstNode;

    cout << listSize << ":";

    while (curNode != lastNode)
    {
        if (curNode->next == lastNode)
            cout << curNode->next->data << endl;
        else
        {
            cout << curNode->next->data << ",";
        }

        curNode = curNode->next;
    }
}


void merge(linkList& a,linkList& b)//合并链表a和b,保存到a中,并降序排序
{
    a.ascendingOrder();//保险起见,先让a,b排序
    b.ascendingOrder();

    listNode* apos=a.firstNode->next;
    listNode* bpos=b.firstNode->next;
    while(bpos!=NULL)
    {
        float tempdata=bpos->data;
        a.tailInsertItem(tempdata);//把b的节点全部插到a中
        bpos=bpos->next;
    }
    a.ascendingOrder();//a升序排序
    a.reverse();//再反转a达到降序排序的效果
}
